//
//  14.链表中倒数第k个节点.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/18.
//

import Foundation
/*
 题目：输入一个链表，输出该链表中倒数第k个结点。如果该链表长度小于k，请返回空。
 思路：双指针法，第一个指针从头先走k-1步，然后第二个指针从头开始和第一个指针一起走，当第一个指针到尾了，此时第二个指针所在位置就是倒数第k个结点
 */
func offer_14() {
    let node1 = Solution.LinkNode(val: 1)
    let node2 = Solution.LinkNode(val: 2)
    let node3 = Solution.LinkNode(val: 3)
    let node4 = Solution.LinkNode(val: 4)
    let node5 = Solution.LinkNode(val: 5)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    print(Solution().findKthToTail(pHead: node1, k: 1)?.val ?? "该链表长度小于k")
}

fileprivate class Solution {
    class LinkNode {
        var val: Int
        var next: LinkNode?
        init(val: Int) {
            self.val = val
        }
    }
    
    func findKthToTail(pHead: LinkNode, k: Int) -> LinkNode? {
        // write code here
        var p1 = pHead
        var p2 = pHead
        for _ in 0..<(k-1) {
            if let next = pHead.next {
                p1 = next
            } else {
                return nil
            }
        }
        while p1.next != nil {
            p1 = p1.next!
            p2 = p2.next!
        }
        return p2
    }
}
